Reduced-Complexity Decoder of Long Reed-Solomon Codes Based on Composite Cyclotomic Fourier Transforms

摘要

Long Reed-Solomon (RS) codes are desirable for digital communication andstorage systems due to their improved error performance, but the highcomputational complexity of their decoders is a key obstacle to their adoptionin practice. As discrete Fourier transforms (DFTs) can evaluate a polynomial atmultiple points, efficient DFT algorithms are promising in reducing thecomputational complexities of syndrome based decoders for long RS codes. Inthis paper, we first propose partial composite cyclotomic Fourier transforms(CCFTs) and then devise syndrome based decoders for long RS codes over largefinite fields based on partial CCFTs. The new decoders based on partial CCFTsachieve a significant saving of computational complexities for long RS codes.Since partial CCFTs have modular and regular structures, the new decoders aresuitable for hardware implementations. To further verify and demonstrate theadvantages of partial CCFTs, we implement in hardware the syndrome computationblock for a $(2720, 2550)$ shortened RS code over GF$(2^{12})$. In comparisonto previous results based on Horner's rule, our hardware implementation notonly has a smaller gate count, but also achieves much higher throughputs.